#define _CRT_SECURE_NO_WARNINGS


#include "Red-BlackTree.h"

//void TestRBTree1()
//{
//	RBTree<int, int> t;
//	// 常规的测试⽤例
//	//int a[] = { 10,5,15,4,6,14,16 };
//	//int a[] = { 16,3,7,11,9,26,18,14,15 };
//	// 特殊的带有双旋场景的测试⽤例
//
//	//int a[] = { 4,2,6,1,3,5,15,7,16,14 };
//	//int a[] = { 25,15,35,10,20,30,40,5,12,11 };
//	for (auto e : a)
//	{
//		t.Insert({ e, e });
//		cout << t.IsValidRBTree() << endl;
//	}
//	t.InOrder();
//	cout << endl;
//	cout << t.IsValidRBTree() << endl;
//}


// 插⼊⼀堆随机值，测试平衡，顺便测试⼀下高度和性能等
void TestRBTree2()
{
	const int N = 10000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << "ms" << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();

	// 擦除确定在的值
	for (auto it = v.begin(); it < v.begin() + 10; it++)
	{
		t.Erase(*it);
	}

	// 随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << "ms" << endl;

	cout << "IsBalance:" << t.IsValidRBTree() << endl;

}
int main()
{
	//TestRBTree1();
	TestRBTree2();

	return 0;
}

